//
// Created by mazaiting on 2021/12/19.
//

#include "seq_search.h"

void Create_SSTable(SSTable **st, int length, int arr[]) {
    // 申请内存
    *st = malloc(sizeof(SSTable));
    // 赋值数据长度
    (*st)->length = length;
    // 申请头内存, 0号预留
    (*st)->elem = malloc((length + 1) * sizeof(SSElemType));
    for (int i = 1; i <= length; ++i) {
        (*st)->elem[i].key = arr[i - 1];
    }
}

int Search_Seq(SSTable *st, int key) {
    // 将关键字作为一个数据元素存放到查找表的第一个位置，起监视哨的作用
    st->elem[0].key = key;
    // 赋值长度
    int len = st->length;
    // 循环查找
    while (st->elem[len].key != key) {
        len--;
    }
    return len;
}

void SSTable_Print(SSTable *st) {
    for (int i = 1; i <= st->length; ++i) {
        printf("%3d", st->elem[i].key);
    }
    printf("\n");
}

int Search_Bin(SSTable *st, int key) {
    // 初始状态 low 指针指向第一个关键字
    int low = 1;
    // high 指向最后一个关键字
    int high = st->length;
    int mid;
    // 判断是否进行查找
    while (low <= high) {
        // mid 每次为取整的整数
        mid = (low + high) / 2;
        if (st->elem[mid].key == key) {
            return mid;
        } else if (st->elem[mid].key > key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return 0;
}
